1. Field of the Invention
This invention relates to a soft output decoding method and apparatus for convolutional codes, applied with advantage to, for example, a satellite broadcast reception device. More particularly, it relates to a soft output decoding device in which the probability information is stored on a recording medium a length not less than a truncated length and in which updating of the probability information within the truncation length and computations of the soft output outside the truncated length are executed in parallel to enable high-speed operations.
2. Description of the Related Art
As a decoding method for minimizing the symbol error ratio following decoding of the convolutional codes, there is known a BCJR algorithm from Bahl, Cocke, Jelinek and Raviv, "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate", IEEE Trans. Information. Theory, Vol. 1T-20, pp. 284 to 287, March 1974. In the BCJR algorithm, it is not each symbol, but the likelihood of each symbol, that is outputted as the decoding result. This output is termed soft output.
Research is being conducted towards reducing the symbol error rate by using soft outputs as decoded output of the inner code of the conjugated code or as outputs of each reiteration of the iterative decoding method. As a decoding method, suited to this purpose, a BCJR algorithm is stirring up notice.
The contents of the BCJR algorithm are hereinafter explained in detail.
The BCJR algorithm outputs the likelihood of each symbol, instead of outputting each symbol, as a decoding result. The BCJR algorithm is used when convolutional encoding the digital information is convolutional-encoded by a convolutional encoder and the resulting data string obtained on convolutional encoding is observed over a non-storage communication route.
M states (transition states) representing the contents of shift registers of a convolutional encoder are expressed as m(0, 1, . . . M/1). The state at time t is S.sub.t, an input at t is I.sub.t, an output at time t is X.sub.t, and an output sequence is X.sub.t.sup.t' =X.sub.t, X.sub.t+1, . . . , X.sub.t'. The transition probability between respective states p.sub.t (m m') is represented by the following equation (1): EQU p.sub.t (m.vertline.m')=Pr{S.sub.t =m.vertline.S.sub.t-1 =m'} (1)
It is noted that Pr{A.vertline.} is a conditional probability of occurrence of A, under a condition that an event B has occurred, while Pr{A;B} is a probability of occurrence of both A and B. It is also assumed that the convolutional codes by the convolutional encoder starts with the state S.sub.0 =0 and outputs X.sub.1.sup..tau. to terminate at S.sub..tau. =0.
The noisy non-storage communication route receives an output X.sub.1.sup..tau. as an input and outputs Y.sub.1.sup..tau.. It is assumed that an output sequence Yt.sup.t' =Y.sub.t, Y.sub.t+1, . . . Y.sub.t'. Meanwhile, the transition probability of the non-storage communication route can be defined, for all t (1.ltoreq.t.ltoreq..tau.), by a function R(.multidot..vertline..multidot.) satisfying the following equation (2): ##EQU1##
Therefore, if the probability .lambda..sub.t is defined as in the following equation (3): ##EQU2##
this probability .lambda..sub.t represents the likelihood of the input information at time t when Y.sub.1.sup..tau. is received, such that this probability .lambda..sub.t is the soft output to be found.
The BCJR algorithm defines the probabilities .alpha..sub.t, .beta..sub.t and .gamma..sub.t as indicated by the following equations (4) to (6): EQU .alpha..sub.t (m)=Pr{S.sub.t =m; Y.sub.1.sup.t } (4) EQU .beta..sub.t (m)=Pr{Y.sub.t+1.sup..tau..vertline.S.sub.t =m} (5) EQU .gamma..sub.t (m'm,i)=Pr{S.sub.t =m;Y.sub.t ;i.sub.t =i.vertline.S.sub.t-1 =m'} (6)
The contents of .alpha..sub.t, .beta..sub.t and .gamma..sub.t are explained with reference to FIG. 1 which illustrates the relation between the respective probabilities. It is noted that .alpha..sub.t-1 corresponds to the probability of passing through respective states at time t-1, as computed based on a reception word as from the encoding starting state S0=0, while .beta..sub.t corresponds to the probability of passing through respective states at time T as computed in the reverse sequence to the chronological sequence based on the reception word as from the encoding end state S.tau.=0, and .gamma..sub.1 corresponds to the reception probability of respective branches in transition through respective states at time t as computed based on the reception word and the input probability at time t.
With the aid of .alpha..sub.t, .beta..sub.t and .gamma..sub.t, the soft output .lambda..sub.t can be represented by the following equation (7): ##EQU3##
It is noted that, for t=1, 2, . . . , .tau., the following equation (8) holds: ##EQU4##
where .alpha..sub.0 (0)=1, .alpha..sub.0 (m)=0(m.noteq.0).
Similarly, the following equation (9): ##EQU5##
holds for t=1, 2, . . . , .tau.-1, where .beta..sub..tau. (0)=1, .beta..sub..tau. (m)=0 (m.noteq.0).
For .gamma..sub.t, the following equation (10) holds: EQU .gamma..sub.t (m', m, i)=P.sub.t (m.vertline.m')R(Y.sub.t, X) in case of transition from m' to m for an input i (X being its output); EQU and EQU .gamma..sub.t (m', m, i)=0 in case of non-transition from m' to m for the input i (10)
Based on the above equation, the BCJR algorithm finds the soft output .lambda..sub.t in accordance with the following sequence (a) to (c):
(a) each time Y.sub.t is received, .alpha..sub.t (m), .gamma..sub.t (m', m, i) is computed using the equations (8) and (10); PA1 (b) after reception of the entire sequence Y.sub.1.sup..tau., .beta..sub.t (m) is computed for respective states m for the totality of time points t, using the equation (9); and PA1 (c) .alpha..sub.t, .beta..sub.t and .gamma..sub.t, computed at (a) and (b), are substituted into the equation (7) to compute the soft output .lambda..sub.t at each time point t. PA1 (a) each time Y.sub.t is received, I.alpha..sub.t (m) and I.gamma..sub.t (m', m, 1) are computed, using the equations (16) and (18); PA1 (b) after receiving the sequence Y.sub.1.sup..tau. in its entirety, I.beta..sub.t (m) is computed, for all states m of all time points t, using the equation (17); PA1 (c) I.alpha..sub.t, I.beta..sub.t and I.gamma..sub.t, computed in (a) to (c), are substituted into the equation (19) to compute the soft output I.lambda..sub.t at each time point. PA1 (a) .gamma..sub.t is found based on the received value at time t and the transition probability; PA1 (b) .beta..sub.t (m) is initialized for the totality of states m so that .beta..sub.t (m)=1/M; PA1 (c) .beta..sub.t-1, . . . , .beta..sub.t-D are computed based on .gamma..sub.t+1, . . . , .gamma..sub.t ; PA1 (d) from .beta..sub.t-D and .alpha..sub.t-D-1, as found, the soft output .lambda..sub.t-D at time t-D is found by the following equation (21): ##EQU9## PA1 (e) from .alpha..sub.t-D-1 and .gamma..sub.t-D, .alpha..sub.t-D is computed.
Meanwhile, the above-described BCJR algorithm suffers from the problem that the volume of computation is considerable because of the product computations involved and that continuous data cannot be received because of the necessity of terminating the codes.
In order to combat these problems, a Max-Log-BCJR algorithm and a log-BCJR algorithm have been proposed as techniques for diminishing the computation volume in Robertson, Villebrun and Hoeher, "A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Domain", in IEEE Int. Cof. On Communications, pp. 1009 to 1013, June 1995, while the SW-BCJR algorithm for performing sliding window processing has been proposed as a technique for receiving continuous data in Benedetto and Montorsi, "Soft-Output Decoding Algorithm in Iterative Decoding of Turbo Codes", TDA Progress Report 42-124, February 1996.
The contents of these algorithms are hereinafter explained.
First, the contents of the Max-Log-BCJR algorithm and the log-BCJR algorithm are explained.
The Max-Log-BCJR algorithm represents the probabilities .alpha..sub.t, .beta..sub.t and .gamma..sub.t, .lambda..sub.t by a modulo 2 logarithm (natural logarithm) and substitutes the logarithmic sum computations for the product processing of the probabilities, as shown in the following equation (11), while approximating the logarithmic sum computations by the logarithmic maximum value computations, as shown in the following equation (12). Meanwhile, max(x, y) is a function which selects a larger one of x or y. EQU Log(e.sup.x.multidot.e.sup.y)=x+y (11) EQU Log(e.sup.x +e.sup.y)=max(x, y) (12)
For simplifying the explanation, logarithms of .alpha..sub.t, .beta..sub.t and .gamma..sub.t, .lambda..sub.1 are set as I.alpha..sub.1, I.beta..sub.t, I.gamma..sub.t, I.lambda..sub.t, respectively, as shown by the following equations (13) to (15): EQU I.alpha..sub.t (m)=log(.alpha..sub.t (m)) (13) EQU I.beta..sub.t (m)=log(.beta..sub.t (m)) (14) EQU I.gamma..sub.t (m)=log(.gamma..sub.t (m)) (15)
where "I" denotes the modulo e logarithm.
In the Max-Log-BCJR algorithm, these I.alpha..sub.t, I.beta..sub.t, I.gamma..sub.t are approximated as shown by the following equations (16) to (18): ##EQU6## ##EQU7## EQU I.gamma..sub.t (m', m, i)=log(P.sub.t (m.vertline.m'))+log(R(Y.sub.t,X)) (18)
where X is an encoder output on transition from m' to m. It is noted that max m' in I.alpha..sub.t (m) and I.beta..sub.t (m) is to be found in the state m' in which transition to a state m occurs for the input i.
Similarly, I.lambda..sub.t is approximated as shown in the following equation (19), in which max m' in the first term of the right side is to be found in the state m' where transition to the state m exists for the input=1 and in which max m' in the second term is to be found in the state m' where transition to the state m exists for the input=0. ##EQU8##
Based on the above relation, the Max-Log-BCJR algorithm finds the soft output .lambda..sub.t in accordance with the following sequence (a) to (c):
Since there are included no product computations in the Max-Log-BCJR algorithm, the processing volume can be reduced significantly in comparison with the BCJR algorithm.
Meanwhile, if the probability sum computation is modified as shown in the following equation (20): EQU Log(e.sup.x +e.sup.y)=max(x, y)+log(1+e.sup.-.vertline.X-Y.vertline.) (20)
the second term of the right side becomes the linear function for the variable .vertline.x-y.vertline., so that, by corresponding tabulation, the logarithmic values of the sum processing can be found correctly.
The Log-BCJR algorithm substitutes the equation (20) for the equation (12) in the Max-Log-BCJR algorithm in its entirety to realize correct probability computations. As compared to the Max-Log-BCJR algorithm, the Log-BCJR algorithm is increased in processing volume. However, there is included no product computation in the Log-BCJR algorithm, such that its output is no other than the logarithmic value of the soft output of the BCJR algorithm except the quantization error.
Since the second term of the right side in the equation (20) is the linear function by the variable .vertline.x-y.vertline., it is possible to obtain simple and highly accurate results of computation by, for example, tabulation. Thus, a soft output higher in accuracy can be obtained with the Log-BCJR algorithm than is possible with the Max-Log-BCJR algorithm.
The contents of the SW-BCJR algorithm are hereinafter explained.
In the BCJR algorithm, the code needs to be terminated for .sub..gamma.t computation, such that continuous data cannot be received. The BCJR algorithm accords 1/M for the totality of states as an initial value of .beta..sub.t, introduces the truncated length as in the case of Viterbi decoding and finds the soft output by retrograding down the time axis by a truncated length D as set (see FIG. 2).
The SW-BCJR algorithm initializes .alpha..sub.0, as in the case of the usual BCJR algorithm, and performs the operations (a) to (e) for each time instant to find the soft output for each time instant.
and
In the above-given thesis by Benedetto et al., there are also proposed a SW-Log-BCJR algorithm, combined from the SW-BCJR algorithm and the Log-BCJR algorithm, and a SW-Max-Log-BCJR algorithm, combined from the SW-BCJR algorithm and the Max-Log-BCJR algorithm. It is noted that the SW-Max-Log-BCJR algorithm is referred to in the thesis as SWAL-BCJR algorithm.
With use of the SW-Max-Log-BCJR algorithm or the SW-Log-BCJR algorithm, it is possible to receive continuous data to find a soft output. However, in these algorithms, in contradistinction from the case of decoding terminated codes, it is necessary to find the number of states multiplied by Y.sub.t for the truncated length in order to find one decoded output, with the result that a large processing volume is involved for mounting even though the product computations are not involved.
The SW-Max-Log-BCJR algorithm or the SW-Log-BCJR algorithm has a drawback that, while it is possible to receive the convolutional encoded and transmitted continuous data to find the soft output, the processing volume for producing a code output is increased to render high-speed processing difficult.
On the other hand, with the SW-Log-BCJR algorithm, combined from the SW-BCJR algorithm and the Log-BCJR algorithm, or the SW-Max-Log-BCJR algorithm, combined from the SW-BCJR algorithm and the Max-Log-BCJR algorithm, also termed the SWAL-MAP algorithm, it is possible to diminish the processing volume to find the soft output of continuous data.
However, with these algorithms, it is necessary to retrograde down the time axis by the truncated length D to produce a soft output to find .beta. for the number of states times the truncated length D, with the result that a tremendous processing volume is required despite the fact that product processing is not involved in the processing.